import math

def euclidean_distance(point1, point2):
    """手动计算欧几里得距离"""
    if len(point1) != len(point2):
        raise ValueError("点的维度不一致")
    
    squared_sum = 0
    for i in range(len(point1)):
        squared_sum += (point1[i] - point2[i]) ** 2
    return math.sqrt(squared_sum)

class KNN:
    def __init__(self, k, label_num):
        self.k = k
        self.label_num = label_num

    def fit(self, x_train, y_train):
        self.x_train = x_train
        self.y_train = y_train

    def get_knn_indices(self, x):
        """手动实现获取K近邻索引"""
        # 计算所有距离
        distances = []
        for i, train_point in enumerate(self.x_train):
            dist = euclidean_distance(train_point, x)
            distances.append((dist, i))
        
        # 手动排序（冒泡排序）
        for i in range(len(distances)):
            for j in range(i + 1, len(distances)):
                if distances[j][0] < distances[i][0]:
                    distances[i], distances[j] = distances[j], distances[i]
        
        # 取前k个索引
        knn_indices = [idx for _, idx in distances[:self.k]]
        return knn_indices

    def get_label(self, x):
        """手动实现类别预测"""
        knn_indices = self.get_knn_indices(x)
        
        # 手动统计类别
        label_statistic = [0] * self.label_num
        for index in knn_indices:
            label = self.y_train[index]
            label_statistic[label] += 1
        
        # 手动找最大值
        max_count = -1
        best_label = -1
        for label, count in enumerate(label_statistic):
            if count > max_count:
                max_count = count
                best_label = label
        
        return best_label

    def predict(self, x_test):
        """手动实现批量预测"""
        predicted_labels = []
        for x in x_test:
            predicted_labels.append(self.get_label(x))
        return predicted_labels

    def score(self, x_test, y_test):
        """手动计算准确率"""
        predictions = self.predict(x_test)
        correct = 0
        for pred, true in zip(predictions, y_test):
            if pred == true:
                correct += 1
        return correct / len(y_test)
